package com.wfm.alg;

/**
 * 树状数组解决某个区间的和问题，还可以对某个下标所对应的值加上某个val后，再求区间值。
 * 添加和查询都是O(logn)
 *
 * 原理:
 * 对某个节点x加上一个val，就要对他的父节点到根节点都加上val。add[1,1]=tr[001]+tr[010]+tr[100]
 * 查询1~x区间和，sum[7]=sum[111]=tr[111]+tr[110]+tr[100]
 *      tr1                       。。。                             tr16
 *      *	*	*	*	*	*	*	*	*	*	*	*	*	*	*	136
 *      *	*	*	*	*	*	*	36
 *      *	*	*	10					*	*	*	42
 *      *	3			*	11			*	19			*	27
 *      1		3		5		7		9		11		13		15
 *      1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
 */
public class P树状数组 {
    public int[] tr;
    public int n;
    public P树状数组(int[] nums){
        n=nums.length;
        tr = new int[n+1];// 下标0不用
        for (int i = 0; i < nums.length; i++) {
            add(i+1,nums[i]);
        }
    }
    public int lowbit(int x){
        return x&-x;
    }
    public void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
    }
    public int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }

}
